CS 5010: Problem Set 6

Out: Monday, February 22, 2016

Due: Monday, February 29, 2016 at 5pm.

Corrected:
Monday, February 22, 9:30pm
Sunday, February 28, 8:40pm (result type for travel-time)

The goal of this problem set is to give you more practice with lists and higher-order functions, and to lay a foundation for subsequent problem sets.

Remember that you must follow the design recipe.

You must use DrScheme's HtDP Intermediate Student Language with Lambda.

As usual, the rubric for grading is here. Remember that you must follow the design recipe. Your deliverables include the data definitions (including interpretation and templates), contract and purpose statements, design strategy, function definitions, and tests. Be sure to sync your work and fill out a Work Session Report at the end of every work session. Use the Work Session Report for PS06.

Required Exercises

This problem set contains two separate problems. The first problem adds three new functions to the trains problem of Problem Set 05. For the second problem, you will define a group of functions for creating and using finite state machines.

For both of these problems, you should use HOFs whenever they improve your code.

(trains-2). For this problem, you will deliver a file named trains-2.rkt that provides all fifteen functions provided by problem 1 of Problem Set 05 and also provides these three new functions:

;;; trains-connect? : ListOfSchedule String String -> Boolean
;;; GIVEN: a list of train schedules and the names of two stations
;;; WHERE: it is not possible to ride forever using the schedules given
;;;     (If you don't understand that restriction, don't worry about it.)
;;; RETURNS: true iff it is possible to go from the first station to the
;;;     second using only the trains described by the schedules
;;; EXAMPLES:
;;;     (trains-connect? empty "Durham, NH" "Newark, NJ")
;;;         => false
;;;     (trains-connect? (list acela-express downeaster)
;;;                                    "Durham, NH" "Newark, NJ")
;;;         => true
;;;     (trains-connect? (list acela-express downeaster)
;;;                                     "Newark, NJ" "Durham, NH")
;;;         => false
;;;     See also the larger examples below.
;;;
;;; itinerary : ListOfSchedule String String -> ListOfSchedule
;;; GIVEN: a list of train schedules and the names of two stations
;;; WHERE: it is possible to go from the first station to the second
;;;     using only the trains described by the schedules, and it is
;;;     not possible to ride forever using the given schedules
;;; RETURNS: a list of abbreviated schedules telling how to get from
;;;     the first station (stn1) to the second (stn2) as fast as possible
;;; WHERE:
;;;     Each abbreviated schedule contains only two station stops,
;;;     which must be in the same order as within the original list
;;;     of stops for the train named in the abbreviated schedule.
;;;     The first station stop for the first abbreviated schedule
;;;     is a stop for stn1.  The last (second) station stop for the
;;;     last abbreviated schedule is a stop for stn2.  For every
;;;     abbreviated schedule except the last in the list, its last
;;;     (second) station stop is for the same station as the first
;;;     station stop in the next abbreviated schedule.  If the
;;;     arrival time for the last stop in an abbreviated schedule
;;;     is less than twenty minutes before the departure time for
;;;     the first stop in the next abbreviated schedule, then a
;;;     layover of 24 hours at that station is implied, and the
;;;     returned list of abbreviated schedules must be the fastest
;;;     when those implied layovers are taken into account.
;;; NOTE:
;;;     There may be several fastest ways to get from the first
;;;     station to the second, in which case the itinerary function
;;;     gets to choose which one of those fastest ways it returns.
;;; EXAMPLES:
;;;     (itinerary (list acela-express downeaster)
;;;                "Durham, NH" "Newark, NJ")
;;;     => (list (make-schedule
;;;               (schedule-name downeaster)
;;;               (list (make-brief-stop (make-train-time 6 25 "A")
;;;                                      "Durham, NH")
;;;                     (make-brief-stop (make-train-time 7 50 "A")
;;;                                      "Boston, MA")))
;;;              (make-schedule
;;;               (schedule-name acela-express)
;;;               (list (make-brief-stop (make-train-time 11 10 "A")
;;;                                      "Boston, MA")
;;;                     (make-brief-stop (make-train-time 3 15 "P")
;;;                                      "Newark, NJ"))))
;;;     See also the larger examples below.
;;;     
;;; travel-time : ListOfSchedule String String -> NonNegInt
;;; GIVEN: a list schedules skeds and the names of two stations stn1 and stn2
;;; WHERE: (trains-connect? skeds stn1 stn2) is true
;;; RETURNS: the number of minutes it takes to get from stn1 to stn2
;;;     (including implied layovers) via the fastest itinerary possible
;;;     using those schedules, as returned by the itinerary function
;;; EXAMPLES:
;;;     (travel-time (list acela-express downeaster)
;;;                  "Durham, NH" "Newark, NJ")
;;;         => 530
;;;     See also the larger examples below.

(define adirondack-nb
  (make-schedule
   "Adirondack (northbound)"
   (list (make-brief-stop (make-train-time  8 15 "A") "New York, NY")
         (make-brief-stop (make-train-time  9 45 "A") "Poughkeepsie, NY")
         (make-stop       (make-train-time 10 50 "A")
                          (make-train-time 11 10 "A")
                          "Albany, NY")
         (make-brief-stop (make-train-time 12 02 "P") "Saratoga Springs, NY")
         (make-brief-stop (make-train-time  3 22 "P") "Plattsburgh, NY")
         (make-brief-stop (make-train-time  7 11 "P") "Montreal, QC"))))

(define empire-service
  (make-schedule
   "Empire Service"
   (list (make-brief-stop (make-train-time 12 05 "P") "Albany, NY")
         (make-brief-stop (make-train-time  1 10 "P") "Poughkeepsie, NY")
         (make-brief-stop (make-train-time  2 45 "P") "New York, NY"))))

(trains-connect? (list downeaster adirondack-nb)
                 "Durham, NH" "Poughkeepsie, NY")                   ; => false
(trains-connect? (list downeaster adirondack-nb acela-express)
                 "Durham, NH" "Poughkeepsie, NY")                   ; => true
(itinerary (list downeaster adirondack-nb acela-express)
           "Durham, NH" "Poughkeepsie, NY")
;;; =>
;;; (list (make-schedule
;;;        (schedule-name downeaster)
;;;        (list (make-brief-stop (make-train-time 6 25 "A") "Durham, NH")
;;;              (make-brief-stop (make-train-time 7 50 "A") "Boston, MA")))
;;;       (make-schedule
;;;        (schedule-name acela-express)
;;;        (list (make-brief-stop (make-train-time 11 10 "A") "Boston, MA")
;;;              (make-stop (make-train-time 2 45 "P")
;;;                         (make-train-time 3 00 "P")
;;;                         "New York, NY")))
;;;       (make-schedule
;;;        (schedule-name adirondack-nb)
;;;        (list (make-brief-stop (make-train-time  8 15 "A") "New York, NY")
;;;              (make-brief-stop (make-train-time  9 45 "A")
;;;                               "Poughkeepsie, NY"))))

(travel-time (list downeaster adirondack-nb acela-express)
             "Durham, NH" "Poughkeepsie, NY")                        ; => 1640

(travel-time (list acela-express empire-service)
             "Poughkeepsie, NY" "Baltimore, MD")                     ; => 1683

(itinerary (list acela-express empire-service)
           "Poughkeepsie, NY" "Baltimore, MD")
;;; =>
;;; (list (make-schedule
;;;        (schedule-name empire-service)
;;;        (list (make-brief-stop (make-train-time  1 10 "P")
;;;                               "Poughkeepsie, NY")
;;;              (make-brief-stop (make-train-time  2 45 "P") "New York, NY")))
;;;       (make-schedule
;;;        (schedule-name acela-express)
;;;        (list (make-stop (make-train-time 2 45 "P")
;;;                         (make-train-time 3 00 "P")
;;;                         "New York, NY")
;;;              (make-brief-stop (make-train-time  5 13 "P")
;;;                               "Baltimore, MD"))))

(fsm-2). For this problem, you will deliver a file named fsm-2.rkt that provides tools for building and using finite state machines.

An InputSymbol is a string of length 1 whose one character is one of the ten decimal digits or one of the 26 lower-case letters "a" through "z".

An InputString is a ListOfInputSymbol. (The InputString represented by the empty list is called epsilon.)

You will need to design Transition and MachineState data types that will be used to describe the state transitions and states of a finite state machine.

Your fsm-2.rkt file must provide the following thirteen functions:

;;; make-transition : InputSymbol String -> Transition
;;; GIVEN: a machine input and the name of a state
;;; RETURNS: a transition representing an edge leading from
;;;     some current state to the given state, labelled by
;;;     the given machine input
;;; EXAMPLES: see examples for transition-label and transition-dest
;;;
;;; transition-label : Transition -> InputSymbol
;;; transition-dest  : Transition -> String
;;; GIVEN: a transition created by make-transition
;;; RETURNS: the corresponding argument that was passed to make-transition
;;; EXAMPLES:
;;;     (transition-label (make-transition "a" "S")) => "a"
;;;     (transition-dest (make-transition "a" "S"))  => "S"
;;;
;;; make-machine-state :
;;;     String Boolean Boolean ListOfTransition -> MachineState
;;; GIVEN: the name of a state, booleans telling whether it is
;;;     a start state and whether it is an accepting state,
;;;     and a list of transitions out of the state
;;; RETURNS: a representation of one state of a finite state machine
;;; EXAMPLES: see examples for the next four functions
;;;
;;; machine-state-name : MachineState -> String
;;; machine-state-is-start? : MachineState -> Boolean
;;; machine-state-is-accepting? : MachineState -> Boolean
;;; machine-state-transitions : MachineState -> ListOfTransition
;;; GIVEN: a machine state created by make-machine-state
;;; RETURNS: the corresponding argument that was passed to make-machine-state
;;; EXAMPLES:
;;;   (machine-state-name (make-machine-state "S0" true false empty))
;;;         => "S0"
;;;   (machine-state-is-start? (make-machine-state "S0" true false empty))
;;;         => true
;;;   (machine-state-is-accepting? (make-machine-state "S0" true false empty))
;;;         => false
;;;   (machine-state-transitions (make-machine-state "S0" true false empty))
;;;         => empty
;;;
;;; machine-state-next : MachineState InputSymbol -> ListOfString
;;; GIVEN: a machine state and an InputSymbol
;;; RETURNS: the set of names (without duplicates, in any order)
;;;     for all machine states that can be reached by taking
;;;     one transition out of the given machine state that's labelled
;;;     by the given input symbol
;;; EXAMPLES:
;;;     (machine-state-next
;;;      (make-machine-state "Q5"
;;;                          false
;;;                          false
;;;                          (list (make-transition "a" "Q5")
;;;                                (make-transition "a" "Q7")
;;;                                (make-transition "b" "Q8")
;;;                                (make-transition "b" "Q5")))
;;;      "a") => some permutation of (list "Q5" "Q7")
;;;
;;;     (machine-state-next
;;;      (make-machine-state "Q5"
;;;                          false
;;;                          false
;;;                          (list (make-transition "a" "Q5")
;;;                                (make-transition "a" "Q7")
;;;                                (make-transition "b" "Q8")
;;;                                (make-transition "b" "Q5")))
;;;      "c") => empty
;;; 
;;; next-states : ListOfMachineState InputSymbol -> ListOfString
;;; GIVEN: a list of machine states and an InputSymbol
;;; RETURNS: the set of names (without duplicates, in any order)
;;;     for all machine states that can be reached by taking
;;;     one transition out of one of the listed machine states
;;;     that's labelled by the given input symbol
;;; EXAMPLES:
;;;     (next-states empty sym) => empty
;;;     (next-states (list state1) sym) => (machine-state-next state1 sym)
;;;     (next-states (list state1 state2) sym)
;;;         => a list representing the set union of
;;;                (machine-state-next state1 sym)
;;;            and (machine-state-next state2 sym)
;;;
;;; is-machine? : ListOfMachineState -> Boolean
;;; GIVEN: a list of machine states
;;; RETURNS: true iff all of the following conditions are true:
;;;     none of the machine states have the same name
;;;     there is exactly one machine state in the list for which
;;;         machine-state-is-start? returns true
;;;     for every machine state in the list, every one of its transitions
;;;         represents a transition to some machine state in the list
;;; EXAMPLES:
;;;     (is-machine? empty) => false
;;;     (is-machine? (list (make-machine-state "S0" true false empty)))
;;;         => true
;;;     (is-machine? (list (make-machine-state "S0" false false empty)))
;;;         => false
;;;     (is-machine?
;;;      (list (make-machine-state
;;;             "S1" false true
;;;             (list (make-transition "a" "S0")
;;;                   (make-transition "a" "S1")
;;;                   (make-transition "b" "S1")))
;;;            (make-machine-state
;;;             "S0" true false
;;;             (list (make-transition "b" "S1")))))
;;;         => true
;;;     (is-machine?
;;;      (list (make-machine-state
;;;             "S1" false true
;;;             (list (make-transition "a" "S0")
;;;                   (make-transition "a" "S2")       ; what's S2 ?
;;;                   (make-transition "b" "S1")))
;;;            (make-machine-state
;;;             "S0" true false
;;;             (list (make-transition "b" "S1")))))
;;;         => false
;;;
;;; A Machine is a ListOfMachineState for which is-machine? returns true.
;;; (For those of you who have taken a course on theory of computation,
;;; a Machine is a nondeterminitic finite automaton (NFA) that has no
;;; epsilon transitions.)
;;;
;;; machine-states-reached-from :
;;;     Machine ListOfMachineState InputString -> ListOfMachineState
;;; GIVEN: a machine, a possibly empty list of machine states belonging
;;;     to the machine, and an input string
;;; RETURNS: the set of machine states (without duplicates, in any order)
;;;     that can be reached from the given machine states by following any
;;;     sequence of transitions that consume the entire input string and
;;;     are allowed by the machine on that input string
;;; EXAMPLES: see below
;;;
;;; machine-accepts? : Machine InputString -> Boolean
;;; GIVEN: a finite state machine and an input string
;;; RETURNS: true iff the set of machine states that can be reached
;;;     from its start state by following transitions allowed by the
;;;     machine on the given input string contains an accepting state
;;;     of the machine
;;; EXAMPLES:

;;; s0 is a start state but not an accepting state

(define s0
  (make-machine-state "S0" true false
                      (list (make-transition "b" "S1"))))

;;; s1 is an accepting state

(define s1
  (make-machine-state "S1" false true
                      (list (make-transition "a" "S0")
                            (make-transition "a" "S1")
                            (make-transition "b" "S2"))))

;;; s2 is neither a start state nor an accepting state

(define s2
  (make-machine-state "S2" false false
                      (list (make-transition "a" "S0"))))

(define nfa1 (list s1 s2 s0))

(is-machine? nfa1) ; => true

(is-machine? (list s0 s1)) ; => false

(next-states (list s1 s2) "b")       ; => (list "S2")
(next-states (list s1) "a")          ; => some permutation of (list "S0" "S1")

(machine-states-reached-from nfa1 (list s1 s2) empty)        ; => (list s1 s2)
(machine-states-reached-from nfa1 (list s1 s2) (list "b"))   ; => (list s2)
(machine-states-reached-from nfa1 (list s1 s2) (list "a"))
    ; => some permutation of (list s0 s1)
(machine-states-reached-from nfa1 (list s1 s2) (list "a" "b" "b"))
    ; => (list s2)

(machine-accepts? nfa1 (list "b" "b" "b")) ; => false
(machine-accepts? nfa1 (list "b" "b" "a")) ; => false
(machine-accepts? nfa1 (list "b" "a" "a")) ; => true

Hints:

Follow the design recipe!! If you write good data definitions, and follow the templates, you will be led to a good solution. If you stray from the templates, you will create a mess. If you are following your templates and still creating a mess, try an alternate path. For example, if you are using the template for one data type, followed immediately by using the template for another data type, and that isn't working for you, try using those templates in the opposite order.
The predefined higher-order functions are your friends. Use them wherever they improve your code. You will be penalized for recursions in your code that could have been simplified and improved by some "obvious" use of a predefined higher-order function.

Last modified: Sun Feb 28 2016